import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// 力扣103. 二叉树的锯齿形层序遍历
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
     }
  }

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node;
                if (leftToRight) {
                    node = queue.pollFirst();
                    if (node.left != null) queue.offerLast(node.left);
                    if (node.right != null) queue.offerLast(node.right);
                } else {
                    node = queue.pollLast();
                    if (node.right != null) queue.offerFirst(node.right);
                    if (node.left != null) queue.offerFirst(node.left);
                }
                currentLevel.add(node.val);
            }

            result.add(currentLevel);
            leftToRight = !leftToRight;
        }

        return result;
    }
}


// 根据中序遍历就可以按照从小到大的顺序遍历，并且求出两不同节点值之间的最小差值
// 力扣530. 二叉搜索树的最小绝对差
class Solution1 {
    private TreeNode prev = null;
    private int minDiff = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        inorderTraversal(root);
        return minDiff;
    }
    private void inorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        inorderTraversal(node.left);
        if(prev != null){
            minDiff = Math.min(minDiff,node.val - prev.val);
        }
        prev = node; // 更新前驱节点
        inorderTraversal(node.right);
    }
}